/**
    time:11-8-6 15:51
    code pratice copy from P. 160 of <Data Structures and Algorithm Analysis in
        C++ Third Edition>
    DataStructure: BinaryHeap
    Version:1.0
*/

#include<vector>
#include<iostream>
#include"dsexceptions.h"
using namespace std;

template <typename Comparable>
class BinaryHeap
{
public:
    explicit BinaryHeap(int capacity);
    explicit BinaryHeap(const vector<Comparable> & items);

    bool isEmpty() const;
    const Comparable & findMin() const;

    void insert(const Comparable & x);
    void deleteMin();
    void deleteMin(Comparable& minItem);
    void makeEmpty();

private:
    int currentSize;    //Number of elements in heap
    vector<Comparable> array;   //The heap array

    void buildHeap();
    void percolateDown(int hole);
};

/**
*   Insert item x,allowing duplicates.
*/
template <typename Comparable>
void BinaryHeap<Comparable>::insert(const Comparable& x)
{
    if(currentSize == array.size()-1)
        array.resize(array.size()*2);

    //Percolate up
    int hole=++currentSize;
    for(; hole>1 && x<array[hole/2]; hole/=2)
        array[hole]=array[hole/2];
    array[hole]=x;
}

/**
*   Remove the minimum item
*   Throws UnderflowException.
*/
template <typename Comparable>
void BinaryHeap<Comparable>::deleteMin()
{
    if(isEmpty())
        throw UnderflowException();

    array[1]=array[currentSize--];
    percolateDown(1);
}

/**
*   Remove the minimum item and place it in minItem.
*   Throws UnderflowException if empty.
*/
template <typename Comparable>
void BinaryHeap<Comparable>::deleteMin(Comparable &minItem)
{
    if(isEmpty())
        throw UnderflowException();

    minItem=array[1];
    array[1]=array[currentSize--];
    percolateDown(1);
}

/**
*   Internal method to percolate down in the heap.
*   hole is the index at which the percolate begins.
*/
template <typename Comparable>
void BinaryHeap<Comparable>::percolateDown(int hole)
{
    int child;
    Comparable tem=array[hole];

    for(; hole*2<currentSize; hole=child)
    {
        child=2*hole;
        if(child!=currentSize && array[child+1]<array[child])
            child++;
        if(array[child]<tem)
            array[hole]=array[child];
        else
            break;
    }
    array[hole]=tem;
}

template <typename Comparable>
BinaryHeap<Comparable>::BinaryHeap( int capacity = 100 )
    : array( capacity + 1 ), currentSize( 0 )
{}

template <typename Comparable>
BinaryHeap<Comparable>::BinaryHeap(const vector<Comparable> &items)
    :array(items.size()+10),currentSize(items.size())
{
    for(int i=0; i<items.size(); i++)
        array[i+1]=items[i];
    buildHeap();
}

/**
*   Establish heap order property from an arbitrary
*   arrangement of items. Runs in linear time.
*/
template <typename Comparable>
void BinaryHeap<Comparable>::buildHeap()
{
    for(int i=currentSize/2; i>0; i--)
        percolateDown(i);
}

/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
template <typename Comparable>
const Comparable & BinaryHeap<Comparable>::findMin( ) const
{
    if( isEmpty( ) )
        throw UnderflowException( );
    return array[ 1 ];
}

template <typename Comparable>
void BinaryHeap<Comparable>::makeEmpty( )
{ currentSize = 0; }

template <typename Comparable>
bool BinaryHeap<Comparable>::isEmpty( ) const
{ return currentSize == 0; }

int main()
{

}
